package com.zk.algorithm;

import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.TouTiao;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
 */
@TouTiao("https://www.nowcoder.com/discuss/147325?type=2&order=0&pos=58&page=1")
@Hard
@LeetCodeExplore("https://leetcode.com/explore/interview/card/top-interview-questions-hard/118/trees-and-graphs/849/")
public class LongestIncreasingPathInAMatrix {

    public static void main(String...args) {
        // 4
        int[][] case1 = new int[][]{
                {3,4,5},
                {3,2,6},
                {2,2,1}
        };

        // 4
        int[][] case2 = new int[][]{
                {9,9,4},
                {6,6,8},
                {2,1,1}
        };

        // 6
        int[][] case3 = new int[][]{
                {7,8,9},
                {9,7,6},
                {7,2,3}
        };

        int[][] case4 = new int[][]{
        };

        System.out.println(new LongestIncreasingPathInAMatrix().longestIncreasingPath(case3));
    }

    public static final int[][] DIRECTION = new int[][] {
            {0,-1}, // LEFT
            {-1,0}, // TOP
            {0,1}, // RIGHT
            {1,0}, // BOTTOM
    };

//    [
//        [9,9,4],
//        [6,6,8],
//        [2,1,1]
//    ]
    public int longestIncreasingPath(int[][] matrix) {
        // 错误点 1
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int max = 1;

        // 增加 Cache 否则会超时
        int[][] cache = new int[matrix.length][matrix[0].length];

        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[r].length; c++) {

                int m = matrix.length;
                int n = matrix[r].length;

                boolean[][] visited = new boolean[m][n];
                for (int k = 0; k < m; k++) {
                    Arrays.fill(visited[k], false);
                }

                max = Math.max(max, doDFS(matrix, r, c, visited, cache));
            }
        }

        return max;
    }

    private int doDFS(int[][] matrix, int r, int c, boolean[][] visited, int[][] cache) {
        if (cache[r][c] != 0) {
            return cache[r][c];
        }

        int max = 1;
        visited[r][c] = true;

        for (int[] dir: DIRECTION) { // 4 个方向探测

            // 错误点 2
            // 写成 dir[0] + 1
            // 写成 dir[1] + 1 了
            int newR = dir[0] + r;
            int newC = dir[1] + c;

            if (newR < 0 || newR >= matrix.length ||
                    newC < 0 || newC >= matrix[newR].length ||
                    matrix[newR][newC] <= matrix[r][c] ||
                    visited[newR][newC]) {
                continue;
            }

            int len = 1 + doDFS(matrix, newR, newC, visited, cache); // 回溯探测
            max = Math.max(len, max);

            // 错误点 3
            // 忘记重置为 false 了
            visited[newR][newC] = false;
        }

        return cache[r][c] = max;
    }

}